#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int reinitializePermutation(int n) {
        vector<int> perm(n);
        int ans = 0;
        for (int i = 0; i < n; i++)
            perm[i] = i;
        vector<int> tmp(perm.begin(), perm.end());
        while (1)
        {
            vector<int> arr(n);
            for (int i = 0; i < n; i++)
            {
                if (i % 2 == 0)
                {
                    arr[i] = perm[i / 2];
                }
                else
                {
                    arr[i] = perm[n / 2 + (i - 1) / 2];
                }
            }
            ans++;
            perm.assign(arr.begin(), arr.end());
            if (perm == tmp)
                break;
        }
        return ans;
    }
};